1. Field of the Invention
This invention relates to adaptive filtering techniques for reducing artifacts in scanned or copied documents that contain images, graphics and/or text. More particularly, this invention relates to methods and apparatuses for selectively applying different types of filters based on local document features to reduce artifacts, such as moirxc3xa9, scanner noise, and/or CCD noise, in documents. The invention also relates to a method of rapidly computing a median filter. The invention further relates to programs of instructions for implementing the adaptive filtering techniques and filter computation method.
2. Description of the Related Art
Many scanned documents are mixed-mode, meaning that they contain at least two of the following types of data: text, graphics and image. When scanned, the scanned representations of such documents may contain artifacts that do not exist in the original. The source of these artifacts varies. If the original document is a screened document, then moirxc3xa9 artifacts may occur in the scanned representation. Other types of artifacts may also appear on scanned representations of mixed-mode documents. Such artifacts include noise that originates from the charge coupled device (CCD) of the scanner or from scanner mechanics.
Moirxc3xa9 artifacts result whenever two geometrically-regular patterns are superimposed. Moirxc3xa9 often manifests itself as a ripple-like pattern in scanned representations of screened documents because the geometrically-regular structure of the screened document is superimposed with the geometrically-regular pattern of scanning.
The nature of the moirxc3xa9 that results from scanning depends on a number of factors including: (1) the resolution of the geometrically-regular structure of the screened document, i.e., the screen frequency, (2) the resolution of the geometrically-regular pattern for the scanning process, i.e., the scan frequency, (3) the relative angle between these two patterns, i.e., the screen angle, and (4) the characteristics of the process used to render the scanned representation. Moirxc3xa9 can be reduced by decreasing the screen frequency, increasing the scan frequency, and/or carefully selecting the screen angle, but these simple techniques are generally unsatisfactory.
A tradeoff between screen frequency and scan frequency is generally unable to achieve a satisfactory reduction in moirxc3xa9 because, on the one hand, a decrease in screen frequency reduces the resolution of the screened document and, on the other hand, an increase in scan frequency greatly increases the amount of resources required to process and store the scanned representation. In some applications such as high-quality printed publications, screen frequencies in excess of 200 lines per inch (about 79 lines per centimeter) are used, making it essentially impossible to reduce moirxc3xa9 by merely increasing the scan frequency.
A careful selection of screen angle is generally unable to achieve a satisfactory reduction in moirxc3xa9 because the angle is difficult to select precisely in many applications. Precise selection is difficult because the relative orientation of the screened image with respect to the orientation of the scanning apparatus is difficult to control precisely. The problem is even greater in color applications where the screen angle for three or more colors must be very carefully selected.
Most methods in the literature use low-pass filtering techniques to reduce moirxc3xa9. While these techniques may reduce moirxc3xa9 artifacts in image regions, they also tend to reduce perceptual quality of text and graphics regions. That is, if a low-pass filter is applied uniformly to the scanned representation, the degree of filtering required to achieve an acceptable reduction in moirxc3xa9 usually results in an unacceptable reduction in resolution. Other methods have been proposed which rely on median filtering. However, such methods may not reduce moirxc3xa9 artifacts as desired.
Thus, there is a need for an effective adaptive filtering technique that produces documents with improved perceptual quality, and that is particularly suitable for mixed-mode documents.
Therefore, it is an object of the present invention to provide improved adaptive filtering techniques that combine various nonlinear filtering techniques to produce documents with improved perceptual quality, and that are particularly useful on scanned or copied representations of mixed-mode documents.
It is another object of this invention to provide improved adaptive filtering techniques which selectively apply different types of filters based on local features to reduce artifacts in scanned or copied representations of mixed-mode documents.
It is a further object of this invention to provide adaptive filtering techniques suited for low- and high-resolution mixed-mode documents, respectively.
It is still another object of this invention to provide a method for fast generation of a median filter.
According to one aspect of this invention, a method for producing an output representation of a mixed-mode document with reduced artifacts is provided. The method comprises computing, for each of a plurality of pixels representing the document, a first average gray scale value of a first pixel neighborhood and a second average gray scale value of a second pixel neighborhood; comparing the difference between the computed first average gray scale value and a value of that pixel with a predetermined threshold value; and based on the result of the comparison, applying either a median filter to the first pixel neighborhood, a first low-pass filter to the second pixel neighborhood, or a second low-pass filter to the first pixel neighborhood, to produce an output representation of the document with reduced artifacts. The method is particularly applicable to a high-resolution representation of a mixed-mode document.
In a preferred embodiment, the first average gray scale value is computed on a 3xc3x973 neighborhood of pixels, centered on but excluding that pixel, and the second average gray scale value is computed on a 3xc3x975 neighborhood centered on and double weighting that pixel.
Preferably, the median filter is applied if the difference between the computed first average gray scale value and the value of that pixel is greater than or equal to the predetermined threshold value, and either the first low-pass filter or the second low-pass filter is applied based on a comparison between (i) the difference between the computed first average gray scale value and a gray scale value of that pixel and (ii) the difference between the computed second average gray scale value and the gray scale value of that pixel.
Preferably, the first low-pass filter is represented by a weighted average gray scale value of the second pixel neighborhood, and the second low-pass filter is represented by an average gray scale value of the first pixel neighborhood.
In another aspect, the invention involves a method for producing an output representation of mixed-mode document with reduced artifacts, that is particularly applicable to a low-resolution representation of such document. The method comprises computing, for each of a plurality of pixels representing the document, a first average gray scale value of a first pixel neighborhood and a second average gray scale value of a second pixel neighborhood; comparing the difference between the computed first average gray scale value and a value of that pixel with a predetermined threshold value; and based on the result of the comparison, applying either a first filter kernel to the first pixel neighborhood, a second filter kernel to the first pixel neighborhood, a third filter kernel to the first pixel neighborhood, a first low-pass filter to the second pixel neighborhood, or a second low-pass filter to the first pixel neighborhood, to produce an output representation of the document with reduced artifacts.
In a preferred embodiment, the first filter kernel is applied if a first sub-condition, indicating that horizontal and vertical edges are to be preserved, is satisfied, the second filter kernel is applied if the first sub-condition is not satisfied but a second sub-condition, indicating that slanted edges are to be preserved, is satisfied, and the third filter kernel is applied if neither the first nor the second sub-condition is satisfied.
Preferably, either the first, second or third filter kernels is applied if the difference between the computed first average gray scale value and the value of that pixel is greater than or equal to the predetermined threshold value, and either the first or second low-pass filter is applied if the difference between the computed first average gray scale value and the value of that pixel is less than the predetermined threshold value.
Preferably, the first low-pass filter, represented by a weighted average gray scale value of the second pixel neighborhood, is applied if the second sub-condition is satisfied, and the second low-pass filter, represented by an average gray scale value of the first pixel neighborhood, is applied if the second sub-condition is not satisfied.
Other aspects of the invention include apparatuses for implementing the adaptive filtering methods described above. Such apparatuses comprise a filter device, an analyzer, and a filter control to perform the processing.
In yet another aspect of the invention, each of the above-described methods may be embodied in a program of instructions (e.g., software) which is stored on, or conveyed to, a computer or other processor-controlled device for execution. Alternatively, the method(s) may be implemented using hardware or a combination of software and hardware.